class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        dp[0] = 0;

        // dp[i] 表示的是和为i的最少完全平方数和的数量

        // dp[1] 表示当n是1时，和为1的完全平方数的最少数量
        // dp[2] 表示当n是2时，和为2的完全平方数的最少数量
        for(int i = 1; i <= n; i++)
        {
            // dp[i] = INT_MAX; 
            dp[i] = i;      // 这里初始化表示每个数都至多能用多少个1加起来，比如dp[5] = 表示1+1+1+1+1 = 5，就是最多完全平方数和的情况了

            // 这里还是循序渐进去求的，想要求n=2得先求n=1，想求n=1得先求n=0
            // 比如下面当i等于1时，1 - 1*1 = 0，表示1就是其中一个完全平方数了
            // 即dp[1] = min(dp[1], dp[1 - 1 * 1] + 1)
            for(int j = 1; j * j <= i; j++)
                dp[i] = min(dp[i], dp[i - j * j] + 1);
        }

        return dp[n];
    }
};